The present invention relates generally to communication systems and iterative decoding performance. A method and apparatus for decoding the serial concatenation of multiple external code blocks with serially concatenated block- and convolutional-coded data is presented. An example of how these concepts may be applied to parallel concatenated codes is also presented.
Communication systems are often limited in terms of transmitter power and spectrum availability. For these and other reasons, it is often a goal of digital communications design to maximize the transmission bit rate R and minimize the probability of bit error, or Bit Error Rate (BER), for a given system power S, and bandwidth B. The minimum bandwidth (BW) required to transmit at rate (R) is known to be Rs/2, where Rs is the symbol rate. A limit on the transmission rate, called the system capacity, is based on the channel BW and the signal to noise ratio (SNR). This limit theorem, also called the Shannon Noisy Channel Coding Theorem, states that every channel has a channel capacity C which is given by the formula, C=BWlog2(1+SNR), and that for any rate R less than C, there exist codes of rate Rc which can have an arbitrarily small decoding BER.
For some time, the digital communications art has sought a coding/decoding algorithm which would reach the Shannon limit. Recently, coding/decoding schemes, called xe2x80x9cTurbo Codes,xe2x80x9d have been determined to achieve fairly reliable data communication at an SNR that is very close to the Shannon Limit for modulation constrained codes.
One form of turbo decoding operates upon serial concatenated codes. Not all of such serially concatenated codes are iteratively decoded in practice, however. As an example, a serial concatenation of an outer, block codexe2x80x94such as a Reed Solomon codexe2x80x94and an inner, convolutional code, can be found in many communications and data storage applications requiring very low bit error rates. This type of serial concatenation is used, for example, in DBS (Direct Broadcast Satellite) standards. However, in practice, this serial concatenated code is not iteratively decoded.
One such serial concatenated system 100 is illustrated in FIG. 1. The serial concatenated system 100 includes a transmitter portion 102 for communicating encoded information to a receiver portion 104 via a communication channel 106. The transmitter portion 102 uses an outer code encoder or block encoder 108 (e.g., a Reed-Solomon encoder) to encode input bits. The output of the outer code encoder 108 is then provided to an interleaver 110 wherein the signal bit order is shuffled in a predetermined manner. Next, the output of the interleaver is provided to an inner code encoder (e.g., convolutional encoder) 112. The output of the inner code encoder 112 is then sent to a bit-to-constellation mapper, modulated by modulator 114 and transmitted over the communication channel 106 to the receiver portion 104 for decoding and processing.
Once demodulated by demodulator 116, the classical approach for decoding a serial concatenated system 100 is to apply a soft-decision inner code decoder (e.g., Viterbi decoder) 118 that receives as inputs soft symbols and outputs hard bit estimates for the inner block code. The outputs of the inner code decoder 118 are then byte-deinterleaved by deinterleaver 120 and provided to an outer code decoder 122 (generally a block decoder such as a Reed-Solomon decoder) that can correct multiple byte errors in a block. If the outer code decoder 122 indicates that the number of errors is beyond its correction capability, it may indicate so and no corrections are made.
In effect, this classical approach to concatenated decoding decomposes the task into two independent procedures: one for the inner code, and another for the outer code. An xe2x80x9coptimalxe2x80x9d decoder is then selected and applied for each of these procedures. However, although each decoder may be optimal for its specific task, the overall composite system may not be optimal for a given concatenated code. This is because (1) the Reed-Solomon decoder uses hard- rather than soft-decision data, and (2) the Viterbi decoder performance could be improved in a second pass decoding operation. In particular, error bursts, which are observed in the first-pass decoding, could be broken up by using the bit decisions from blocks which were successfully decoded by a Reed-Solomon decoder. This operation would, in turn, impact a second-pass Reed-Solomon decoding of the data, perhaps enabling the Reed-Solomon decoder to correct another block that previously was considered uncorrectable. In principle, the sharing of outer-to-inner code decoding information could be re-iterated, resulting in even further improvements. In fact, this technique is similar to turbo decoding in a parallel or serial concatenated code context, with bit-by-bit maximum a posteriori probability (MAP) decoding.
Various iterative (turbo-like) decoding approaches have been used in simulation to decode serial concatenations of convolutional and Reed-Solomon codes. One problem in such decoding processes is determining how the Viterbi algorithm is to be modified to accommodate inputs from Reed-Solomon decoded blocks that are correct. One attractive approach involves finding a method that efficiently forces a Viterbi decoder to constrain certain locations in a data record to desired output logic levels.
As previously indicated, the aforesaid serial concatenation of a Reed Solomon and a convolutional code can be iteratively decoded. However, better results are achievable if the component codes are specifically designed with the iterative decoding process in mind. xe2x80x98Turbo codesxe2x80x99 are examples of such codes.
A limitation of conventional turbo decoders is the inability to reach very low bit error rate (BER) floors; this inhibits their broad application to video transport, which requires very low BERs. One approach employed in the art to try to reduce the BER floor has been geared towards choosing good codes and topologies. These approaches try to make more efficient the already existent methods of trying to perform turbo decoding, but sometimes practical implementations that achieve the desired level of performance are difficult to find. For this reason, the serial concatenation of an additional, external decoder, such as a Reed-Solomon decoder, is sometimes used in an attempt to drive the BER floor lower. For some applications, whereby only the turbo code is used, one may not be able to achieve sufficiently low BER floors as desired or required within a given application.
Further limitations and disadvantages of conventional and traditional systems will become apparent to one of skill in the art through comparison of such systems with the present invention as set forth in the remainder of the present application with reference to the drawings.
Various aspects of the present invention can be found in a turbo decoder that employs iterative decoding, and additionally employs a turbo code-external xe2x80x98external decoderxe2x80x99 in the iterative decoding process. This external decoder may be a decoder for an error detection code, such as a block Cyclic Redundancy Check (CRC) code, or a block algebraic error correction code, such as a Reed Solomon or BCH code. Multiple external code xe2x80x9csub-blocksxe2x80x9d (upon which the CRC or Reed Solomon decoder operate upon) exist within a single block being decoded by the turbo decoder.
Other aspects of the invention can be seen in a conventional serial concatenation of a convolutional code with a Reed Solomon or similar algebraic decoder. In fact, the role and utilization of the Reed Solomon, or xe2x80x98other similar algebraic coderxe2x80x99 is analagous to the external decoder within the turbo decoder application. The only difference is that the xe2x80x98external codexe2x80x99 is married with a turbo code in the turbo code application; whereas, the xe2x80x98external codexe2x80x99 is married with a convolutional code in the conventional serial concatenation case.
The invention involves the feedback of high-confidence xe2x80x98correctxe2x80x99 hard decisions from an external decoder to the turbo decoder (or convolutional decoder). More importantly, it outlines techniques by which information concerning these high confidence decisions may be imposed as constraints and thereby exploited within the turbo decoder (or convolutional decoder).
The feedback from the external decoder is employed within one or both of the inner and/or the outer decoder (SISO) of a serial turbo concatenated codexe2x80x94or the inner code of a conventional concatenated code. The method for employment for this feedback information within the SISOs may involve one or both of decision-forcing and/or input data overloading. Decision-forcing may be characterized as a method that renormalizes selective state metrics so that the decoder is prohibited from considering undesired decision outcomes. Input data overloading may be characterized as muxing input data with extreme values, so that this data can be overwritten in selected locations, and thereby influence the decoder to favor desired decision outcomes. Moreover, various aspects of the invention are applicable to areas beyond those of serially concatenated codes. One such extension includes their application using a parallel concatenated code.
Other systems, methods, features and advantages of the invention will be or will become apparent to one with skill in the art upon examination of the following figures and detailed description. It is intended that all such additional systems, methods, features and advantages be included within this description, be within the scope of the invention, and be protected by the accompanying claims.